// 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

// 示例:

// 输入: 

// 1 0 1 0 0
// 1 0 1 1 1
// 1 1 1 1 1
// 1 0 0 1 0

// 输出: 4

#include <vector>
#include <algorithm>

using namespace std;

/* 动态规划
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        int res{0}; // 边长
        vector<vector<int>> dp(m, vector<int>(n, 0)); // dp[i][j]表示以i,j为右下角的最大正方形边长
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    if ((i == 0) || (j == 0)) {
                        dp[i][j] = 1; // 边界情况
                    } else {
                        dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    }
                    if (dp[i][j] > res) res = dp[i][j];
                }
            }
        }
        return res * res;
    }
};